Certain embodiments of the present invention generally relate to systems and methods for calculating navigation routes based on map databases indicative of adjacent geographic regions.
Route planning systems are well known in the field of navigational instruments. Route planning systems in general define one or more paths through a network of roads between source and destination locations. The path(s) planned by the system may be based on one or more criteria, such as shortest distance, shortest time, user preferences and the like. Several algorithms are known for performing route planning, with such algorithms calculating the route from the source or destination location or from both simultaneously. Conventional planning algorithms operate based on a predefined stored map database, which includes data indicative of a geographic region containing the source and destination locations.
In general, each map database corresponds to a particular geographic region, such as a city, a county, a state, a country, a continent, etc. Each map database contains data indicative of features within the associated geographic region with varied levels of specificity concerning the features. In general, map databases representing smaller geographic regions (e.g. cities) contain more detailed feature information (county roads, city streets, restaurants, and the like), while map databases representing larger geographic regions (e.g. states and countries) contain less detailed feature information (e.g. interstates, state highways, gas stations, hotels, rest stops, and the like). The feature information stored within each map database may include geographic coordinates (i.e. altitude, longitude and latitude) among other things. Each map database is bound by a geographic region perimeter or boundary that is intersected by roads of the roadway network that extend beyond the boundary.
Conventionally, a navigable network is comprised of roads, ferry routes, and possibly other means to travel from one location in the network to another. Conventionally the navigable network is described as a collection of intersections (know as nodes) of navigable features and links, arcs or paths (road, ferry, etc.) connecting nodes. Thus, the navigable network is viewed as a collection of nodes, at each of which a travel direction decision may be made, and a collection of links or arcs connecting the nodes and describing a travel path from one node to another. The term adjacency is conventionally used to describe the travel path and nodes reachable in the network from a given node. A solution between two points in the network involves iteratively examining the adjacencies from the start and destination points in the network, eventually xe2x80x9cdiscoveringxe2x80x9d a low-cost path. Several well-known algorithms are designed to solve this problem, such as the A-star algorithm, various shortest path algorithms and the like.
Presently, cartographic information is charted or mapped by data suppliers as large cartographic data blocks. A single cartographic data block may include detailed maps for multiple adjoining metropolitan areas and/or detailed maps for large geographic areas and the like. A cartographic data block is typically divided by the data suppliers, by manufactures of the routing devices or by service providers into smaller map databases having a size more conducive to storage on, or wireless transmission to, a navigation or route planning device. By way of example only, a large block of cartographic data may constitute a detailed map of the metropolitan corridor for the East coast between Washington, D.C. and Boston. The cartographic data block may be divided into a first map database for the Washington, D.C. metropolitan area, a second map database for the Baltimore metropolitan area, a third map database for the Philadelphia metropolitan area, and so on. Unfortunately, a route cannot currently be charted using two separate map databases. For example, a route cannot be charted from an address located in Washington D.C. to a destination located in Baltimore using the aforementioned map databases.
Hence, conventional navigation and route planning devices are unable to plan routes between source and destination locations that are located in separate map databases, even if the separate map databases are adjacent to one another. Because conventional navigation and route planning devices are only able to calculate paths between sources and destinations in a single map database, the user is required to separately enter source and destination locations within each discrete map database. Stated another way, conventional systems provide map databases to describe the roadway network within a specific selected geographic area, but do not provide a means for the node exploration step to continue into adjacent geographic areas.
A need exists for improved navigation and route planning devices capable of automatically calculating routes between a single source location and a single destination location based on adjacent map databases. A need exists for a navigation device capable of accessing adjacent map databases to plan a route.
It is a goal of certain embodiments of the present invention to enable node exploration to continue into adjacent geographic areas, effectively enabling a route to be computed through an arbitrary number of separately constructed, but adjacent, networks.
Certain embodiments of the present invention relate to a method for providing a navigation route between two locations. The method includes providing first and second data maps of different geographic regions. A group of potential paths are planned from the first location through the first geographic region based on the first data map. When each potential path intersects an edge of the first data map, a transition point in the second data map is identified based on the location where a current potential path intersects the edge of the first data map. The current potential path is further planned from the transition point into and/or through the second geographic region, based on the second data map, towards the second location. Optionally, the data maps may constitute first and second map databases which include data indicative of a roadway network or of nodes at which the roads intersect edges of the data maps. The method locates node coordinates where the roadway network intersects an edge of the first data map. The node coordinates may be used to identify the transition point. The data indicative of the node coordinates, at which roads intersect the edges of the first and second data maps, may be compared to identify the transition point in the second data map. The node coordinates are stored in an edge table associated with the second data map. Edge tables are searched for node coordinates which match the location where the current potential path intersects the edge of the first data map.
Optionally, multiple data maps may be analyzed corresponding to the geographic regions adjacent to the first geographic region, and one of the data maps may be selected as the second data map. The two adjacent data maps may be identified by organizing multiple data maps into a bounded box layout. To continue planning the current potential path through the second data map, node expansions are performed by looking at the nodes in the second data map that are linked to the transition point.
In accordance with another embodiment, a map database is recorded on a computer readable medium. The map database includes nodal records stored in a linked structure. The nodal records contain data indicative of nodes in a roadway network located in a geographic region within defined boundaries. Data indicative of the roads that intersect and join other nodes is also stored. Optionally, the nodal records may identify the nodes, the distance to the adjacent nodes, and the speed data for the roads connecting the nodes. The nodal records also include edge markers which indicate which nodes intersect the boundaries of the geographic region. The nodal records are stored in a manner to facilitate a match between adjacent map databases. The map database may further include an edge table that contains longitude and latitude coordinates indicating where the roads intersect the boundaries, or other data which identifies each road.
Edge/route coordinates which identify where roads intersect a boundary may be stored in a searchable format. The edge/route coordinates for one of the boundaries matches the edge/route coordinates stored in the map database for an adjacent boundary of an adjoining geographic region.
In accordance with another embodiment, a portable electronic device is provided. The device includes a memory, a processor and an output unit. The memory stores data maps of roadway networks for geographic regions that are surrounded by edges. The memory may store data indicative of roads in the roadway networks and nodes where the roads intersect the edges. The processor explores for potential paths through a first data map until the exploration intersects an edge of the data map. Then the processor automatically shifts the potential path exploration to a second data map. Upon successful route calculation, the output unit presents the route through the first and second data maps to a user. The device may further include a display to present the maps to the user.
The processor may identify a transition point to the second data map based on a location at which the current potential path intersects the edge of the first data map. Alternatively, the processor may locate the node coordinates of a location where the current potential path intersects an edge of the first data map and use the node coordinates to identify a transition point to the second data map. The data indicative of node coordinates may be compared where roads intersect the edges of the first and second data maps. Alternatively, the processor may search an edge table associated with the second data map for the node coordinates that match the location where the current potential path intersects the edge of the first data map.
The processor may organize the multiple data maps into a bounded box layout that identifies adjacent data maps. The processor may perform a node expansion by looking at the nodes in the second data map that are linked to the transition point to continue planning the current potential path through the second data map. The processor may identify an edge node in the first data map where the current potential path intersects the edge of the first data map and analyze the adjacent nodes in the second data map to shift the calculation of the current potential path to the second data map. The adjacent nodes constitute nodes in the second data map that directly connect roads to the edge nodes of the first data map.
In accordance with another embodiment, a navigation system is provided for calculating a route between two locations. The navigation system includes an input unit that accepts the first and second locations from a user. A memory is included that stores at least the first and second map databases that contain data indicative of two adjacent geographic regions. A route planner is also included. The route planner calculates potential paths from the first location through the first geographic region based on the first map database. When a current potential path intersects an edge of the first geographic region, the route planner accesses the second map database to continue calculating the current potential path toward the second location through the second geographic region that is based on the second data map. The first and second geographic regions may partially overlap one another. The memory may store edge tables that contain coordinates identifying nodes on the edges of the first geographic region that overlap the second geographic region.